CF 2059 div.2

📅Date: 2025-02-10 📚Category: 算法竞赛 📂Tags: Codeforces div2 📑Word: 13.8k

CF 2059 div.2

A Milya and Two Arrays

题目大意

给出两个长度相同的数组 \(A,B\), 每个数组中的元素均重复出线现(即若 \(x\in A\), 则 \(x\) 在 \(A\) 中出现次数大于等于 \(2\)).

现在定义 \(C_i=A_i+B_i\), 问是否可以通过对 \(A\) 的重新排列, 使得 \(C\) 中不同元素个数不少于 \(3\) 种.

题解

手玩几个小样例不难发现, 无解当且仅当 \(A,B\) 各自不同元素种类的个数和小于等于 \(3\).

代码

const int N = 55;
int n, a[N], b[N];
void solve()
{
    read(n);
    int mx = 0, mn = 1e9, cnt = 0;
    for (int i = 1; i <= n; i++)
        read(a[i]);
    sort(a + 1, a + n + 1);
    cnt += unique(a + 1, a + n + 1) - a - 1;
    for (int i = 1; i <= n; i++)
        read(b[i]);
    sort(b + 1, b + n + 1);
    cnt += unique(b + 1, b + n + 1) - b - 1;
    puts(cnt <= 3 ? "NO" : "YES");
}
int main()
{
    int T = 1;
    cin >> T;
    while (T--)
        solve();
    flushout();
    return 0;
}

B Cost of the Array

题目大意

给出一个长为 \(n\) 的数组和一个偶数 \(k\), 现在需要将该数组分成 \(k\) 段子数组 (每段均连续). 接着将所有偶数段取出拼成新数组 \(B\), 并在末尾加入数字 \(0\). 定义花费为最小的 \(i\) 满足 \(B_i\neq i\). 求最小花费.

题解

  • 当 \(n=k\) 时, 划分方式唯一, 直接模拟求解即可.

  • 当 \(n\neq k\) 时, 答案不超过 \(2\). 首先我们希望第二段的开头不是 \(1\), 所以如果第 \(2\) 个数到第 \(n-k+2\) 个数中有不是 \(1\) 的数, 我们直接以此为第二段开头即可, 否则由于 \(k\) 是偶数, 第 \(2,3,4\) 位一定均是 \(1\) (n-k+2\geq 4), 所以直接取前 \(4\) 位单独成段即可 (k\geq 4). 而当 \(k=2\) 时, 说明该数组全是 \(1\).

代码

const int N=2e5+10;
int n,k,a[N];
void solve()
{
    read(n),read(k);
    for(int i=1;i<=n;i++)read(a[i]);
    if(n==k)
    {
        for(int i=2;i<=n;i+=2)
        {
            if(a[i]!=i/2)
            {
                write(i/2);
                return;
            }
        }
        write(k/2+1);
        return;
    }
    for(int i=2;i<=n-k+2;i++)
        if(a[i]!=1)
        {
            write(1);
            return;
        }
    write(2);
    return;
}
int main()
{
    int T;
    cin>>T;
    while(T--) solve();
    flushout();
    return 0;
}

C Customer Service

题目大意

有 \(n\) 条服务队列, 初始都为 \(0\) 个人, 接下来一共有 \(n\) 个时刻, \(a_{i,j}(a_{i,j}\geq 1)\) 表示第 \(i\) 个队列在 \(j\) 时刻来的客人.

并且在每个时刻来人后, 你必须选择恰好一条队列并将其清空.

请求出在这 \(n\) 个时刻后, 这 \(n\) 条队列最终人数的 \(\text{MEX}\) 最大是多少.

题解

首先考虑只有最后一个时刻被清空的队列是 \(0\), 因为 \(a_{i,j}\geq 1\). 而想要最终是 \(1\) 个人, 那么 \(a_{i,n}=1\) 且在 \(n-1\) 时刻清空该队列. 如此重复可以得到最终是 \(k\) 个人的队列一定满足最后 \(k\) 个时刻来的人都是 \(1\) 个人并且在第 \(k-1\) 时刻将其清空.

由此, 我们求出每条队列末尾连续 \(1\) 的长度, 然后从小到大贪心选取即可.

代码

const int N = 310;
int T, n, a[N][N], b[N];

int main()
{
    read(T);
    while (T--)
    {
        read(n);
        for (int i = 1; i <= n; i++)
            b[i] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                read(a[i][j]);
        for (int i = 1; i <= n; i++)
            for (int j = n; j; j--)
                if (a[i][j] == 1)
                    b[i]++;
                else
                    break;
        sort(b + 1,b+n+1);
        int ans = 0;
        for(int i=1;i<=n;i++)
            if(b[i]>=ans)ans++;
        write(ans);
    }
    flushout();
    return 0;
}

D Graph and Graph

题目大意

给出两个均含有 \(n\) 个结点的无向图, 分别含有 \(m_1\), \(m_2\) 条边, 现在你在这两张图上各有一个初始结点 \(s_1\), \(s_2\). 每一次操作你都可以选择和你当前位置相邻的结点并移动过去 (两张图上均要移动). 设操作后你的位置是 \(u_1,u_2\) 那么你这次操作的花费是 \(|u_1-u_2|\). 问在这样的操作规则下操作无限步后你的花费最小是多少, 如果是无穷请输出 \(-1\).

题解

简单最短路题, 我们先考虑最后不是无穷的情况, 一定是有一条边在两个图中均存在, 并且可以做到在两张图上同时达到编号相同的一个端点上 (这里面其实蕴含了一个奇偶性，但对实际做题没有影响). 考虑到一共只有 \(n^2\) 个点对, 我们只要从 \((s_1,s_2)\) 从出发, 跑最短路, 当遇到上述不是无穷的情况就可以更新答案.

考虑边数一定不超过 \(m_1\times m_2\), 所以复杂度是 \(\text{O}((n + m_1\times m_2)\log(m_1\times m_2))\). 可以通过.

代码

const int N = 1e3 + 10;
int T, n, s1, s2, m1, m2, dis[N][N];
vector<int> e1[N], e2[N];
void graph_read(int &m, vector<int> *e)
{
    read(m);
    for (int i = 1, u, v; i <= m; i++)
    {
        read(u), read(v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    return;
}
struct nod
{
    int u1, u2, dis;
    bool operator<(const nod &b) const
    {
        return dis > b.dis;
    }
};

priority_queue<nod> q;

int main()
{
    read(T);
    while (T--)
    {
        read(n), read(s1), read(s2);
        for (int i = 1; i <= n; i++)
            e1[i].clear(), e2[i].clear();
        graph_read(m1, e1);
        graph_read(m2, e2);
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dis[i][j] = 1e9 + 10;
        dis[s1][s2] = 0;
        q.push({s1, s2, 0});
        int ans = 2e9;
        while (!q.empty())
        {
            nod now = q.top();
            q.pop();
            if (now.dis != dis[now.u1][now.u2])
                continue;
            for (int t1 : e1[now.u1])
                for (int t2 : e2[now.u2])
                {
                    if (now.u1 == now.u2 && t1 == t2)
                        ans = min(ans, now.dis);
                    if (dis[t1][t2] > now.dis + abs(t1 - t2))
                    {
                        dis[t1][t2] = now.dis + abs(t1 - t2);
                        q.push({t1, t2, dis[t1][t2]});
                    }
                }
        }
        write(ans == 2e9 ? -1 : ans);
    }
    flushout();
    return 0;
}

E Stop Gaming

题目描述

给你 \(n\) 个数组, 每个数组的长度为 \(m\). 让 \(i\)-th 数组中的 \(j\)-th 元素表示为 \(a_{i, j}\).保证所有 \(a_{i, j}\) 都是不同的. 在一次操作中, 您可以执行以下操作:

  • 选择某个整数 \(i\) ( \(1 \le i \le n\) ) 和一个整数 \(x\) ( \(1 \le x \le 2 \cdot n \cdot m\) ).

  • 对于从 \(i\) 到 \(n\) 依次递增的所有整数 \(k\), 进行以下操作:

    1. 将元素 \(x\) 添加到 \(k\)-th 数组的开头.

    2. 将 \(k\)-th 数组中最后一个元素的值赋值给 \(x\).

    3. 删除 \(k\)-th 数组中的最后一个元素.

换句话说, 你可以在任意数组的开头插入一个元素, 之后这个数组和后面所有数组中的元素都会向右平移一个. 最后一个数组的最后一个元素会被移除.

此外, 我们还给出了目标数组 \(b_{i,j}\). 保证 \(b_{i,j}\) 互不相同, 求最少的操作次数将 \(a_{i,j}\) 变为 \(b_{i,j}\). 并输出具体方案.

题解

我们先考虑求最少的次数. 这是一个贪心的过程, 因为我们希望尽可能的利用原本就存在的数. 那么我们来考虑能被利用的数的性质, 首先被利用的数肯定是 \(b_{i,j}\) 的子序列. 其次, 这些数应该是 \(a_{i,j}\) 的前缀, 因为根据上述操作, 我们无法间隔的留下 \(a_{i,j}\).

那么我们就希望这个前缀尽可能长, 于是考虑从左至右贪心, 找到最远的可行位置. 一个位置是可行的一方面, 其左边所有需要操作的位置都"经历过" \(k\) 的倍数, 只有这样才能在该位置后面添数, 这部分就对应了代码中 tot < m - (i - 2 + m) % m - 1 && dlt 这部分. 当无法达到时直接结束. 而另一方面, 该位置后面可能也需要添加元素, 所以该位置也得"经历过" \(k\) 的倍数, 对应了代码中的 tot >= m - (i - 1 + m) % m - 1. 要注意的是, 不满足该条件也需要继续往后找, 因为后面可能有位置合法.

如此往复, 我们就可以得到最长的前缀, 然后减一下就得到最少步数.

第二部分, 求具体方案. 当我们知道长度后其实就是模拟这个过程, 考虑用线段树作为辅助数据结构, 要进行区间加减, 全局查询最右边的 \(0\) (意味着该位置需要被操作了, 并且操作该位置不会影响左边的可操作性). 当某个位置操作完时, 将其赋值为 \(\text{inf}\) 即可. 而当全局最小值不是 \(0\) 后意味着操作结束.

代码

const int N = 3e5 + 10;
int T, n, m, a[N], b[N], cnt[N], ct[N], val[N], pos[N];
map<int, int> mp;
struct Tree
{
    int mn, pos, tag;
    void upd(int tg)
    {
        mn += tg;
        tag += tg;
        return;
    }
} tr[N << 2];
void pushup(int rt)
{
    if (tr[ls].mn < tr[rs].mn)
    {
        tr[rt].mn = tr[ls].mn;
        tr[rt].pos = tr[ls].pos;
    }
    else
    {
        tr[rt].mn = tr[rs].mn;
        tr[rt].pos = tr[rs].pos;
    }
    return;
}
void pushdown(int rt)
{
    if (tr[rt].tag)
    {
        tr[ls].upd(tr[rt].tag);
        tr[rs].upd(tr[rt].tag);
        tr[rt].tag = 0;
    }
}
void build(int rt, int l, int r)
{
    tr[rt] = {0, 0, 0};
    if (l == r)
    {
        tr[rt] = {val[l], l, 0};
        return;
    }
    int mid = (l + r) / 2;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    pushup(rt);
}
void change(int rt, int l, int r, int L, int R, int v)
{
    if (L <= l && r <= R)
        return tr[rt].upd(v);
    pushdown(rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        change(ls, l, mid, L, R, v);
    if (mid < R)
        change(rs, mid + 1, r, L, R, v);
    pushup(rt);
    return;
}
int main()
{
    read(T);
    while (T--)
    {
        read(n), read(m);
        mp.clear();
        // mp[0] = n * m + 1;
        for (int i = 1; i <= n * m; i++)
            read(a[i]);
        for (int i = 1; i <= n * m; i++)
            read(b[i]), mp[b[i]] = i;
        for (int i = 1; i <= n * m; i++)
            pos[i] = mp[a[i]];
        int len = 0;
        for (int i = 1, tot = 0; i <= n * m; i++)
        {
            if (pos[i - 1] >= pos[i])
                break;
            int dlt = pos[i] - pos[i - 1] - 1;
            cnt[i - 1] = dlt;
            val[i - 1] = cnt[i - 1] ? m - (i - 2 + m) % m - 1 : 1e9;
            if (tot < m - (i - 2 + m) % m - 1 && dlt)
                break;
            tot += dlt;
            if (tot >= m - (i - 1 + m) % m - 1)
                len = i;
        }
        cnt[len] = n * m - pos[len];
        val[len] = cnt[len] ? m - (len - 1 + m) % m - 1 : 1e9;
        for (int i = 0; i <= len; i++)
            ct[i] = cnt[i];
        write(n * m - len);
        build(1, 0, len);
        while (tr[1].mn == 0)
        {
            int now = tr[1].pos;
            write((now + m - 1) / m + 1, ' '), write(b[pos[now] + ct[now]]);
            if ((--ct[now]) == 0)
                change(1, 0, len, now, now, 1e9);
            if (now < len)
                change(1, 0, len, now + 1, len, -1);
        }
    }
    flushout();
    return 0;
}

评论